The rapidly increasing commercial importance of efficient, real-time generation of high resolution graphics images and scenes from digital data bases has sparked a significant amount of work in the areas of graphics display processor and frame buffer device architecture and in developing faster linear expression evaluation techniques.
Many of the computational tasking performed in conventional raster-scan graphics systems, aside from texturing, includes determining the relationship of a point (typically representing a pixel or a sub-pixel) to a specific line as defined in a two or three dimensional space. These linear expression evaluations are typically conducted by generating a mathematical definition of a particular line in the form of Ax+By+C and inserting a selected coordinate pair of x, y point or pixel values into the linear expression as so defined.
Increases in the efficiency and speed of evaluating linear expressions of the form mentioned above, therefore, offer the potential to significantly shorten the time required to develop and prepare digitally generated images and scene frames for presentation in real-time on a graphics screen display.
Conventional raster scan graphics display systems typically support the NTSC standard frame generation rate of thirty frames per second. Real-time digital scene generators are thus, in general, limited to less than one thirtieth of a second to compute and prepare the content of each successive frame. As a 512 by 512 pixel display screen requires that information for over 250 thousand pixels be provided in each frame, usually at the NTSC rate of thirty frames per second as in conventional quality video systems, improvements in the speed of frame generation, and reductions in the cost of high speed frame generation, are of fundamental value to manufacturers of electronic products and systems intended for application in the fields of electronic media based entertainment, multimedia and virtual reality.
Conventional techniques for creating a graphics frame scene include accessing one or more digitally stored objects from a data base library. These stored objects essentially are mathematical models that are defined in data bases as individual sets of planar polygons. These planar polygons are typically further defined by sets of vertices located in a three dimensional space.
The image of an object in a particular scene is determined by the stored mathematical model of the object, the position of the object within the environment of a particular frame, the hypothetical viewing position of an observer, and a selected field of view. The three latter parameters are typically set by an interactive applications program.
Generated images are then clipped to either conform with a specified field of view or as a result of processing constraints. The clipping process may create more edges and the need for significantly more computational work later in the conventional art.
The image is then scaled for perspective and integrated into a full digital scene frame. Transformation of polygon vertices coordinates into screen coordinates and sorting out occlusion effects typically are accomplished during the integration of an image into the full scene.
Coloring, shading and texturing computations for each pixel are carried out at various steps within the conventional art process of most real time digital scene generation systems.
The computational operations used to determine distances, surfaces, shading, lighting, coordinate transformations and texture coordinates are essentially linear expression evaluations. In fact, and as mentioned previously, much of the computational load of a real time digital scene generator aside from texturing primarily involves linear expression evaluation.
An article by Henry Fuchs et al., published in the Association for Computing Machinery's SIGGRAPH '85, pp. 111-120, entitled "Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes" discloses a logic-enhanced memory system architecture designed for raster graphics imaging systems. This specialized digital circuit architecture, specifically identified as Pixel-Planes, provides logic-enhanced memory chips as elements of the frame buffer. These logic-enhanced memory chips store scanned out images and perform pixel level calculations. A binary tree of one bit adders efficiently computes a given linear expression for the x and y of every pixel of the screen display.
A frame buffer memory chip designed in accordance with the Pixel-Planes concept comprises a unified multiplier tree connected to a multiplicity of pixel dedicated, logic enhanced memory segments. Each of these memory segments is made up of a one bit arithmetic logic unit (ALU), a one bit Enable register, and a set allotment of memory bits, perhaps 32 or 72. Each memory segment is dedicated to a particular pixel within a region. The region lay-out, and permanent assignment of individual memory segments to pixel locations within a region, is defined by the memory device architecture (i.e. individually and permanently hard-wired.)
The Pixel-Planes concept provides for a translator circuit which receives polygon vertex coordinates from a transformation engine board. The translator circuit converts the vertex coordinates into the A, B, and C coefficients of a linear expression, where the an x1, y1 coordinate pair of a vertex v1, and an x2, y2 coordinate pair of a vertex v2 yield an A coefficient equal to y1 minus y2, a B coefficient equal to x2 minus x1, and a C value equal to the product of x1 and y2, less the product of x2 and y1.
The value of the calculation of the resultant Ax+By+C equation is positive for a given pixel if and only if the pixel is on the same side of the line as the polygon surface. In the Pixel-Planes operating technique, all Enable registers are set to a "1" value at the initiation of each individual polygon examination. Should a pixel fall outside of any edge of the polygon under examination, that pixel's corresponding Enable register is changed to a "0" value.
The Pixel-Planes technique divides a full frame into a series of regions. A two dimensionally assigned stack of logic-enhanced memory segments (i.e. a hardware set includes a one bit ALU, a one bit Enable register, and a strip of memory) sequentially process each region of a particular frame.
The logic-enhanced memory segments are assigned within a region to a permanent x, y coordinate value pair. This permanent assignment of x, y values to a logic-enhanced memory segment, and the relative isolation of a logic-enhanced memory segment, especially in being restricted to drawing only upon its' own computing resources during most of its' operations, may limit optimal application of the total computing power of the Pixel-Planes hardware to efficiently process the numerous contribution layers of a typical frame preparation.
Further developments of Pixel-Planes concepts have led to the issuance of two patents of note to Henry Fuchs, of the Computer Science Department of the University of North Carolina, and another related patent to Henry Fuchs and John W. Poulton of Durham, N.C. U.S. Pat. No. 4,590,465, issued to Henry Fuchs on May 20, 1986, discloses a raster scan type graphics system that permits simultaneous calculations at every pixel in a polygon. Multiplier trees generate values for every Ax, By and C for every value of x and y in the pixel matrix. The x, y coordinates are defined within this patent as being the coordinates of the pixel within the image, and are permanently assigned to a logic-enhanced memory segment, as described in the SIGGRAPH '85 article discussed above. A special purpose computer is required to generate the Ax, By and C values.
U.S. Pat. No. 4,783,649, issued to Henry Fuchs and John W. Poulton on Nov. 8, 1988, discloses a graphics display image buffer which is supportive of economical implementation of the Pixel-Planes concept as embodied in U.S. Pat. No. 4,590,465 and as mentioned above. The apparatus of this later patent comprises the combination of the x and y multiplier trees, which are then connected to a conventional IC memory grid design. Each output of the x-y multiplier tree is available to the pixel dedicated logic enhanced memory segments.
U.S. Pat. No. 4,827,445, issued to Henry Fuchs on May 2, 1989, discloses an alternative image buffer comprising logic-enhanced pixel memory cells. A processor at each cell, as envisioned in this patent, performs pixel color and other values for the polygons. Memory cells are presented in this patent as being in direct correspondence to one specific pixel (within a sequentially moving region) of the screen.
In reference to all three patents described above, the Pixel-Planes design and processing concepts limit logic-enhanced memory segments/cells to receiving computing support only from a multiplier tree or trees, but to otherwise function without further resources beyond individual segment/cell computing capabilities.
Two patents issued to Poulton et al., U.S. Pat. Nos. 5,388,206 and 5,481,669, also relate to image generation through use of a plurality of processing elements. The Poulton et al. image generation system utilized a composition network which interconnected a number of rendering and shading and texturing devices.
While the above systems and methods distributed the image generation across a number of logic enhance memory devices or processors, these systems may still have processing bottlenecks based upon the distribution of primitives within a screen.